﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PojProject.Pojs
{
    public class Poj1068
    {
        private int[] parenthesesArray;

        private List<int> moniArray;

        public Poj1068(int[] parenthesesArray)
        {
            this.parenthesesArray = parenthesesArray;

            PopulateMoni();
        }

        private void PopulateMoni()
        {
            moniArray = new List<int>();

            int preItem = 0;
            foreach (var item in parenthesesArray)
            {
                for (int i = 0; i < item - preItem; i++)
                {
                    moniArray.Add(-1);
                }

                moniArray.Add(1);
                preItem = item;
            }
        }

        // I can use -1 to indicate the left-parenthese, and 1 to indicate the right-parenthese. 
        // here I don't care that is value (I just the right-parenthese's value should be bigger than left-parenthese's)
        public IEnumerable<int> Play()
        {
            // 这里比较有意思的是， 我用一组匹配（左括号，右括号） 右括号的位置减去左括号的位置+1 /2 就是中间有多少括号。
            Dictionary<int, int> pairs = new Dictionary<int, int>();

            // store the left-parenthese position.
            Stack<int> leftParenthesesRecord = new Stack<int>();

            int testCase = 0;
            for (int i = 0; i < moniArray.Count; i++)
            {
                int temp = testCase;
                testCase += moniArray[i];

                if (testCase > temp)
                {
                    pairs.Add(leftParenthesesRecord.Pop(), i);
                }
                else
                {
                    leftParenthesesRecord.Push(i);
                }
            }

            return pairs.Select(x => (x.Value - x.Key + 1) / 2);
        }
    }
}
